//https://leetcode.cn/problems/reducing-dishes/description/?envType=daily-question&envId=2023-10-22


class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        int n = satisfaction.size(), ans = 0;
        sort(satisfaction.begin(), satisfaction.end());
        if(satisfaction[0] >= 0)
            for(int i = 0; i < n; i++)
                ans += satisfaction[i] * (i + 1);
        else
            for(int i = 0; i < n && satisfaction[i] < 0; i++){
                int sum = 0;
                for(int j = i; j < n; j++)
                    sum += satisfaction[j] * (j - i + 1);
                ans = max(ans, sum);
            }
        return ans;
    }
};